#include "il2cpp-config.h"
#include "object-internals.h"
#include "vm/Monitor.h"

#if IL2CPP_SUPPORT_THREADS

#include "os/Atomic.h"
#include "os/Event.h"
#include "os/Semaphore.h"
#include "os/Thread.h"
#include "vm/Exception.h"
#include "vm/Thread.h"

#include "utils/ThreadSafeFreeList.h"

#include <cassert>
#include <limits>


using namespace il2cpp;


// Mostly follows the algorithm outlined in "Implementing Fast Java Monitors with Relaxed-Locks".

/// State of a lock associated with an object.
///
/// Allocated from the normal non-GC heap and kept on a free list. This means that an object that is
/// not unlocked before it is reclaimed will leak its monitor. However, it allows us to not have to
/// synchronize with the GC and to efficiently reuse a small number of monitor instances between an
/// arbitrary number of managed objects.
///
// NOTE: We do *NOT* allow deletion of monitors as threads may be hanging on to monitors even as they
//	are already back on the free list (and maybe even in use somewhere else already).
struct MonitorData : public utils::ThreadSafeFreeListNode
{
	static const os::Thread::ThreadId kCanBeAcquiredByOtherThread = os::Thread::kInvalidThreadId;
	static const os::Thread::ThreadId kHasBeenReturnedToFreeList = (os::Thread::ThreadId) -1;

	/// ID of thread that currently has the object locked or one of the two values above.
	///
	/// This signals three possible states:
	///
	/// 1) Contains a valid thread ID. Means the monitor is owned by that thread and only that thread can
	///    change the value of this field.
	/// 2) Contains kCanBeAcquiredByOtherThread. Means monitor is still live and attached to an object
	///    but is up for grabs by whichever thread manages to swap the value of this field for its own
	///    thread ID first.
	/// 3) Contains kHasBeenReturnedToFreeList. Means monitor is not attached to any object and can be
	///    acquired by any thread *but* only through the free list.
	ALIGN_TYPE (8) volatile uint64_t owningThreadId;

	/// Number of times the object has been locked on the owning thread. Everything above 1 indicates
	/// a recursive lock.
	/// NOTE: This field is never reset to zero.
	uint32_t recursiveLockingCount;

	/// Semaphore used to signal other blocked threads that the monitor has become available.
	/// The "ready queue" is implicit in the list of threads waiting on this semaphore.
	os::Semaphore semaphore;

	/// Number of threads that are already waiting or are about to wait for a lock on the monitor.
	volatile uint32_t numThreadsWaitingForSemaphore;

	/// Event that a waiting thread fires to acknowledge that it has been kicked off a monitor by the thread
	/// already holding a lock on the object being waited for. This happens when the locking thread decides
	/// to deflate the locked object and thus kill the monitor but then some other thread comes along and
	/// decides to wait on the monitor-to-be-killed.
	os::Event flushAcknowledged;

	/// Node in list of waiting threads.
	///
	/// Memory management is done the same way as for MonitorData itself. The same constraints apply.
	/// Wait nodes are returned to the free list by the threads that have created them except for abandoned
	/// nodes which may be returned by the pulsing thread.
	///
	/// NOTE: Every wait node must be cleaned up by the wait thread that allocated it.
	struct PulseWaitingListNode : public utils::ThreadSafeFreeListNode
	{
		enum State
		{
			/// Node is waiting to be reused.
			kUnused,
			/// Node is waiting to be signaled.
			kWaiting
		};

		/// Next node in "threadsWaitingForPulse" list.
		/// NOTE: Once on the list, this field may only be modified by the thread holding a lock
		///       on the respective monitor.
		PulseWaitingListNode* nextNode;

		/// Event to notify waiting thread of pulse.
		il2cpp::os::Event signalWaitingThread;

		/// Current usage state. This is not set atomically. Change this state only if you
		/// are at a known sequence point.
		int32_t state;

		static il2cpp::utils::ThreadSafeFreeList<PulseWaitingListNode> s_FreeList;

		PulseWaitingListNode ()
			: nextNode (NULL)
			, state (kUnused) {}

		void Release ()
		{
			state = kUnused;
			signalWaitingThread.Reset();
			s_FreeList.Release (this);
		}

		static PulseWaitingListNode* Allocate ()
		{
			PulseWaitingListNode* node = s_FreeList.Allocate ();
			assert (node->state == kUnused);
			return node;
		}
	};

	/// List of threads waiting for a pulse on the monitor.
	/// NOTE: This field may be modified concurrently by several threads (no lock).
	PulseWaitingListNode* threadsWaitingForPulse;

	static il2cpp::utils::ThreadSafeFreeList<MonitorData> s_FreeList;

	MonitorData ()
		: owningThreadId (kHasBeenReturnedToFreeList)
		, recursiveLockingCount (1)
		, numThreadsWaitingForSemaphore (0)
		, threadsWaitingForPulse (NULL)
		, semaphore (0, std::numeric_limits<int32_t>::max ())
	{
	}

	bool IsAcquired () const
	{
		return (owningThreadId != kCanBeAcquiredByOtherThread && owningThreadId != kHasBeenReturnedToFreeList);
	}

	bool TryAcquire (uint64_t threadId)
	{
		return (os::Atomic::CompareExchange64 (&owningThreadId, threadId, kCanBeAcquiredByOtherThread) == kCanBeAcquiredByOtherThread);
	}

	void Unacquire ()
	{
		assert (owningThreadId == os::Thread::CurrentThreadId ());
		os::Atomic::Exchange64 (&owningThreadId, kCanBeAcquiredByOtherThread);
	}

	/// Mark current thread as being blocked in Monitor.Enter(), i.e. as "ready to acquire monitor
	/// whenever it becomes available."
	void AddCurrentThreadToReadyList ()
	{
		os::Atomic::Increment (&numThreadsWaitingForSemaphore);
		vm::Thread::SetState (vm::Thread::Current (), vm::kThreadStateWaitSleepJoin);
	}

	/// Mark current thread is no longer being blocked on the monitor.
	int RemoveCurrentThreadFromReadyList ()
	{
		int numRemainingWaitingThreads = os::Atomic::Decrement (&numThreadsWaitingForSemaphore);
		vm::Thread::ClrState (vm::Thread::Current (), vm::kThreadStateWaitSleepJoin);
		return numRemainingWaitingThreads;
	}
	
	/// Acknowledge that the owning thread has decided to kill the monitor (a.k.a. deflate the corresponding
	/// object) while we were waiting on it.
	void VacateDyingMonitor ()
	{
		RemoveCurrentThreadFromReadyList ();
		flushAcknowledged.Set ();
	}

	void PushOntoPulseWaitingList (PulseWaitingListNode* node)
	{
		// Change state to waiting. Safe to not do this atomically as at this point,
		// the waiting thread is the only one with access to the node.
		node->state = PulseWaitingListNode::kWaiting;

		// Race other wait threads until we've successfully linked the
		// node into the list.
		while (true)
		{
			PulseWaitingListNode* nextNode = threadsWaitingForPulse;
			node->nextNode = nextNode;
			if (os::Atomic::CompareExchangePointer (&threadsWaitingForPulse, node, nextNode) == nextNode)
				break;
		}
	}

	/// Get the next wait node and remove it from the list.
	/// NOTE: Calling thread *must* have the monitor locked.
	PulseWaitingListNode* PopNextFromPulseWaitingList ()
	{
		assert (owningThreadId == os::Thread::CurrentThreadId ());

		PulseWaitingListNode* head = threadsWaitingForPulse;
		if (!head)
			return NULL;

		// Grab the node for ourselves. We take the node even if some other thread
		// changes "threadsWaitingForPulse" in the meantime. If that happens, we don't
		// unlink the node and the node will stay on the list until the waiting thread
		// cleans up the list.
		PulseWaitingListNode* next = head->nextNode;
		if (os::Atomic::CompareExchangePointer (&threadsWaitingForPulse, next, head) == head)
			head->nextNode = NULL;

		return head;
	}

	/// Remove the given waiting node from "threadsWaitingForPulse".
	/// NOTE: Calling thread *must* have the monitor locked.
	bool RemoveFromPulseWaitingList (PulseWaitingListNode* node)
	{
		assert (owningThreadId == os::Thread::CurrentThreadId ());

		// This function works only because threads calling Wait() on the monitor will only
		// ever *prepend* nodes to the list. This means that only the "threadsWaitingForPulse"
		// variable is actually shared between threads whereas the list contents are owned
		// by the thread that has the monitor locked.

	  tryAgain:
		PulseWaitingListNode* previous = NULL;
		for (PulseWaitingListNode* current = threadsWaitingForPulse; current != NULL; )
		{
			// Go through list looking for node.
			if (current != node)
			{
				previous = current;
				current = current->nextNode;
				continue;
			}

			// Node found. Remove.
			if (previous)
				previous->nextNode = node->nextNode;
			else
			{
				// We may have to change "threadsWaitingForPulse" and thus have to synchronize
				// with other threads.
				if (os::Atomic::CompareExchangePointer (&threadsWaitingForPulse, node->nextNode, node) != node)
				{
					// One or more other threads have changed the list.
					goto tryAgain;
				}
			}
			node->nextNode = NULL;

			return true;
		}

		// Not found in list.
		return false;
	}
};

utils::ThreadSafeFreeList<MonitorData> MonitorData::s_FreeList;
utils::ThreadSafeFreeList<MonitorData::PulseWaitingListNode> MonitorData::PulseWaitingListNode::s_FreeList;

static MonitorData* GetMonitorAndThrowIfNotLockedByCurrentThread (Il2CppObject* obj)
{
	// Fetch monitor data.
	MonitorData* monitor = os::Atomic::ReadPointer (&obj->monitor);
	if (!monitor)
	{
		// No one locked this object.
		vm::Exception::Raise (vm::Exception::GetSynchronizationLockException ("Object is not locked."));
	}

	// Throw SynchronizationLockException if we're not holding a lock.
	// NOTE: Unlike .NET, Mono simply ignores this and does not throw.
	uint64_t currentThreadId = os::Thread::CurrentThreadId ();
	if (monitor->owningThreadId != currentThreadId)
	{
		vm::Exception::Raise (vm::Exception::GetSynchronizationLockException
			("Object has not been locked by this thread."));
	}

	return monitor;
}

namespace il2cpp
{
namespace vm
{

void Monitor::Enter (Il2CppObject* object)
{
	TryEnter (object, std::numeric_limits<uint32_t>::max ());
}

bool Monitor::TryEnter (Il2CppObject* obj, uint32_t timeOutMilliseconds)
{
	uint64_t currentThreadId = os::Thread::CurrentThreadId ();

	while (true)
	{
		MonitorData* installedMonitor = os::Atomic::ReadPointer (&obj->monitor);
		if (!installedMonitor)
		{
			// Set up a new monitor.
			MonitorData* newlyAllocatedMonitorForThisThread = MonitorData::s_FreeList.Allocate ();
			assert (os::Atomic::Read64 ((int64_t*) &newlyAllocatedMonitorForThisThread->owningThreadId) == MonitorData::kHasBeenReturnedToFreeList
					&& "Monitor on freelist cannot be owned by thread!");
			os::Atomic::Exchange64 (&newlyAllocatedMonitorForThisThread->owningThreadId, currentThreadId);

			// Try to install the monitor on the object (aka "inflate" the object).
			if (os::Atomic::CompareExchangePointer (&obj->monitor, newlyAllocatedMonitorForThisThread, (MonitorData*) NULL) == NULL)
			{
				// Done. There was no contention on this object. This is
				// the fast path.
				assert (obj->monitor);
				assert (obj->monitor->recursiveLockingCount == 1);
				assert (obj->monitor->owningThreadId == currentThreadId);
				return true;
			}
			else
			{
				// Some other thread raced us and won. Retry.
				os::Atomic::Exchange64 (&newlyAllocatedMonitorForThisThread->owningThreadId, MonitorData::kHasBeenReturnedToFreeList);
				MonitorData::s_FreeList.Release (newlyAllocatedMonitorForThisThread);
				continue;
			}
		}

		// Object was locked. See if it us already having a lock.
		if (os::Atomic::Read64 (&installedMonitor->owningThreadId) == currentThreadId)
		{
			// Yes, recursive lock. Just increase count.
			++installedMonitor->recursiveLockingCount;
			return true;
		}

		// Getting an immediate lock failed, so if we have a zero timeout now,
		// entering the monitor failed.
		if (timeOutMilliseconds == 0)
			return false;

		// Object was locked by other thread. Let the monitor know we are waiting for a lock.
		installedMonitor->AddCurrentThreadToReadyList ();
		if (os::Atomic::ReadPointer (&obj->monitor) != installedMonitor)
		{
			// Another thread deflated the object while we tried to lock it. Get off
			// the monitor.
			// NOTE: By now we may already be dealing with a monitor that is back on the free list
			//	or even installed on an object again.
			installedMonitor->VacateDyingMonitor ();

			// NOTE: The "Implementing Fast Java Monitors with Relaxed-Locks" paper describes a path
			//	that may lead to monitors being leaked if the thread currently holding a lock sees our
			//  temporary increment of numWaitingThreads and ends up not deflating the object. However,
			//  we can only ever end up inside this branch here if the locking thread has already decided to
			//  deflate, so I don't see how we can leak here.

			// Retry.
			continue;
		}

		// NOTE: At this point, we are in the waiting line for the monitor. However, the thread currently
		//	locking the monitor may still have already made the decision to deflate the object so we may
		//	still get kicked off the monitor.

		// Wait for the locking thread to signal us.
		while (os::Atomic::ReadPointer (&obj->monitor) == installedMonitor)
		{
			// Try to grab the object for ourselves.
			if (installedMonitor->TryAcquire (currentThreadId))
			{
				// Ownership of monitor passed from previously locking thread to us.
				assert (installedMonitor->recursiveLockingCount == 1);
				assert (obj->monitor == installedMonitor);
				installedMonitor->RemoveCurrentThreadFromReadyList ();
				return true;
			}

			// Wait for owner to signal us.
			os::WaitStatus waitStatus;
			try
			{
				if (timeOutMilliseconds != std::numeric_limits<uint32_t>::max ())
				{
					// Perform a timed wait.
					waitStatus = installedMonitor->semaphore.Wait (timeOutMilliseconds, true);
				}
				else
				{
					// Perform an infinite wait. We may still be interrupted, however.
					waitStatus = installedMonitor->semaphore.Wait (true);
				}
			}
			catch (...)
			{
				// This is paranoid but in theory a user APC could throw an exception from within Wait().
				// Just make sure we clean up properly.
				installedMonitor->RemoveCurrentThreadFromReadyList ();
				throw;
			}

			////TODO: adjust wait time if we have a Wait() failure and before going another round

			if (waitStatus == os::kWaitStatusTimeout)
			{
				// Wait failed. Get us off the list.
				int newNumWaitingThreads = installedMonitor->RemoveCurrentThreadFromReadyList ();
				
				// If there are no more waiting threads on this monitor, we need to check for leaking.
				// This may happen if the locking thread has just been executing a Monitor.Exit(), seen
				// the positive numWaitingThread count, and decided that it thus cannot deflate the object
				// and will trigger the semaphore. However, we've just decided to give up waiting, so if
				// we were the only thread waiting and no one ever attempts to lock the object again, the
				// monitor will stick around with no one ever deflating the object.
				//
				// We solve this by simply trying to acquire ownership of the monitor if we were the last
				// waiting thread and if that succeeds, we simply change from returning with a time out
				// failure to returning with a successful lock.
				if (!newNumWaitingThreads && os::Atomic::ReadPointer (&obj->monitor) == installedMonitor)
				{
					if (installedMonitor->TryAcquire (currentThreadId))
					{
						// We've successfully acquired a lock on the object.
						assert (installedMonitor->recursiveLockingCount == 1);
						assert (obj->monitor == installedMonitor);
						return true;
					}
				}

				// Catch the case where a timeout expired the very moment the owning thread decided to
				// get us to vacate the monitor by sending an acknowledgement just to make sure.
				if (os::Atomic::ReadPointer (&obj->monitor) != installedMonitor)
					installedMonitor->flushAcknowledged.Set ();
				
				return false;
			}
		}

		// Owner has deflated the object and the monitor is no longer associated with the
		// object we're trying to lock. Signal to the owner that we acknowledge this and
		// move off the monitor.
		installedMonitor->VacateDyingMonitor ();
	}

	return false;
}

void Monitor::Exit (Il2CppObject* obj)
{
	// Fetch monitor data.
	MonitorData* monitor = GetMonitorAndThrowIfNotLockedByCurrentThread (obj);

	// We have the object lock. Undo one single invocation of Enter().
	int newLockingCount = monitor->recursiveLockingCount - 1;
	if (newLockingCount > 0)
	{
		// Was recursively locked. Lock still held by us.
		monitor->recursiveLockingCount = newLockingCount;
		return;
	}

	// See if there are already threads ready to take over the lock.
	if (os::Atomic::Add (&monitor->numThreadsWaitingForSemaphore, 0) != 0)
	{
		// Yes, so relinquish ownership of the object and signal the next thread.
		monitor->Unacquire ();
		monitor->semaphore.Post ();
	}
	else if (monitor->threadsWaitingForPulse)
	{
		// No, but there's threads waiting for a pulse so we can't deflate the object.
		// The wait nodes may already have been abandoned but that is for the pulsing
		// and waiting threads to sort out. Either way, if there ever is going to be a
		// pulse, *some* thread will get around to looking at this monitor again so all
		// we do here is relinquish ownership.
		monitor->Unacquire ();
	}
	else
	{
		// Seems like no other thread is interested in the monitor. Deflate the object.
		os::Atomic::ExchangePointer (&obj->monitor, (MonitorData*) NULL);

		// At this point the monitor is no longer associated with the object and we cannot safely
		// "re-attach" it. We need to make sure that all threads still having a reference to the
		// monitor let go of it before we put the monitor back on the free list.
		//
		// IMPORTANT: We still *own* the monitor at this point. No other thread can acquire it and
		//	we must not let go of the monitor until we have kicked all other threads off of it.

		monitor->flushAcknowledged.Reset ();
		while (os::Atomic::Add (&monitor->numThreadsWaitingForSemaphore, 0) != 0)
		{
			monitor->semaphore.Post (monitor->numThreadsWaitingForSemaphore);
			// If a thread starts waiting right after we have read numThreadsWaitingForSemaphore,
			// we won't release the semaphore enough times. So don't wait spend a long time waiting
			// for acknowledgement here.
			monitor->flushAcknowledged.Wait (1, false);
		}

		// IMPORTANT: At this point, all other threads must have either already vacated the monitor or
		//   be on a path that makes them vacate the monitor next. The latter may happen if a thread
		//   is stopped right before adding itself to the ready list of our monitor in which case we
		//   will not see the thread on numThreadsWaitingForSemaphore. If we then put the monitor back
		//   on the freelist and then afterwards the other thread is resumed, it will still put itself
		//   on the ready list only to then realize it got the wrong monitor.
		//   So, even for monitors on the free list, we accept that a thread may temporarily add itself
		//   to the wrong monitor's ready list as long as all it does it simply remove itself right after
		//   realizing the mistake.

		// Release monitor back to free list.
		assert (monitor->owningThreadId == os::Thread::CurrentThreadId ());
		os::Atomic::Exchange64 (&monitor->owningThreadId, MonitorData::kHasBeenReturnedToFreeList);
		MonitorData::s_FreeList.Release (monitor);
	}
}

static void PulseMonitor (Il2CppObject* obj, bool all = false)
{
	// Grab monitor.
	MonitorData* monitor = GetMonitorAndThrowIfNotLockedByCurrentThread (obj);

	bool isFirst = true;
	while (true)
	{
		// Grab next waiting thread, if any.
		MonitorData::PulseWaitingListNode* waitNode = monitor->PopNextFromPulseWaitingList ();
		if (!waitNode)
			break;

		// Pulse thread.
		waitNode->signalWaitingThread.Set ();

		// Stop if we're only supposed to pulse the one thread.
		if (isFirst && !all)
			break;

		isFirst = false;
	}
}

void Monitor::Pulse (Il2CppObject* object)
{
	PulseMonitor (object, false);
}

void Monitor::PulseAll (Il2CppObject* object)
{
	PulseMonitor (object, true);
}

void Monitor::Wait (Il2CppObject* object)
{
	TryWait (object, std::numeric_limits<uint32_t>::max ());
}

bool Monitor::TryWait (Il2CppObject* object, uint32_t timeoutMilliseconds)
{
	MonitorData* monitor = GetMonitorAndThrowIfNotLockedByCurrentThread (object);

	// Undo any recursive locking but remember the count so we can restore it
	// after we have re-acquired the lock.
	uint32_t oldLockingCount = monitor->recursiveLockingCount;
	monitor->recursiveLockingCount = 1;

	// Add us to the pulse waiting list for the monitor (except if we won't be
	// waiting for a pulse at all).
	MonitorData::PulseWaitingListNode* waitNode = NULL;
	if (timeoutMilliseconds != 0)
	{
		waitNode = MonitorData::PulseWaitingListNode::Allocate ();
		monitor->PushOntoPulseWaitingList (waitNode);
	}

	// Release the monitor.
	Exit (object);
	monitor = NULL;

	// Wait for pulse (if we either have a timeout or are supposed to
	// wait infinitely).
	os::WaitStatus pulseWaitStatus = os::kWaitStatusSuccess;
	Il2CppException* exceptionThrownDuringWait = NULL;
	if (timeoutMilliseconds != 0)
	{
		pulseWaitStatus = os::kWaitStatusFailure;
		try
		{
			vm::ThreadStateSetter state (vm::kThreadStateWaitSleepJoin);
			pulseWaitStatus = waitNode->signalWaitingThread.Wait (timeoutMilliseconds, true);
		}
		catch (Il2CppExceptionWrapper& exception)
		{
			// Exception occurred during wait. Remember exception but continue with reacquisition
			// and cleanup. We re-throw later.
			exceptionThrownDuringWait = exception.ex;
			pulseWaitStatus = os::kWaitStatusFailure;
		}
	}

	////TODO: deal with exception here
	// Reacquire the monitor.
	Enter (object);

	// Monitor *may* have changed.
	monitor = object->monitor;

	// Restore recursion count.
	monitor->recursiveLockingCount = oldLockingCount;

	// Get rid of wait list node.
	if (waitNode)
	{
		// Make sure the node is gone from the wait list. If the pulsing thread already did
		// that, this won't do anything.
		monitor->RemoveFromPulseWaitingList (waitNode);
		
		// And hand it back for reuse.
		waitNode->Release ();
		waitNode = NULL;
	}

	// If the wait was interrupted by an exception (most likely a ThreadInterruptedException),
	// then re-throw now.
	//
	// NOTE: We delay this to until after we've gone through the reacquisition sequence as we
	//	have to guarantee that when Monitor.Wait() exits -- whether successfully or not --, it
	//  still holds a lock. Otherwise a lock() statement around the Wait() will throw an exception,
	//  for example.
	if (exceptionThrownDuringWait)
		vm::Exception::Raise (exceptionThrownDuringWait);

	////TODO: According to MSDN, the timeout indicates whether we reacquired the lock in time
	////	and not just whether the pulse came in time. Thus the current code is imprecise.
	return (pulseWaitStatus != os::kWaitStatusTimeout);
}

bool Monitor::IsAcquired (Il2CppObject* object)
{
	MonitorData* monitor = object->monitor;
	if (!monitor)
		return false;

	return monitor->IsAcquired ();
}

} /* namespace vm */
} /* namespace il2cpp */


#endif // IL2CPP_SUPPORT_THREADS
